1. Field of the Invention
The present disclosure relates generally to efficient processes for the filtering of IP packet prefixes and more specifically to an efficient process for identifying which Internet Protocol prefixes are stored in a RIB maintained by a network protocol.
2. Description of Related Art
Large communication networks are typically comprised of multiple autonomous systems that are administered by a single organization or entity, and each autonomous system can include multiple sub-networks or subnets each of which is a distinct, logical part of the autonomous system. Each subnet can include some number of packet network devices such as routers and/or switches and some number of host devices such as servers and/or clients that cooperate to transport information from one location to another location in the network. In order to transport information from one location to another in a network, such as the Internet, an IP address is pre-pended to each transmitted packet or frame of information. This IP address is divided into a network portion or network prefix and a host portion, with the network prefix portion occupying the N (N being a number from 1 to 32 for IPv4) most significant bits of the address and with the host portion occupying the N least significant bits of the address. The network portion of the IP address is used by routers or switches to determine to which portion of the network (subnet) a packet or frame with a particular network prefix is sent, and the host portion is used by the routers or switches to determine to which particular host (server or client) the packet is sent.
In order to operate within a network to forward information to the correct destination, packet network devices learn reachability information from other packet network devices with which they can communicate. This information can include, among other things, the network prefix information of the surrounding network devices. This network prefix information is typically learned by a network protocol running on a packet network device. Any particular network device can include one or more network protocols such as the open shortest path first (OSPF) protocol, the border gateway protocol (BGP), the routing information protocol (RIP) to name only three. This network reachability information is then employed by the various network protocols to build a routing information base (RIB) which a routing table manager can use to build a common forwarding information base (FIB).
In addition to being used to build RIBs and FIBs, network prefixes can be used to define policies which are employed by a packet network device to accept or deny packets it receives from other areas of the network in which it is located or from other protocols as the result of route redistribution. More specifically, prefixes can be used to filter incoming and outgoing network update information used by network protocols such as BGP and OSPF, and prefixes can be used to control the redistribution of routing information from one network protocol to another, such as between OSPF and RIP or between OSPF and BGP, whether the different protocols are running on the same network device or on different network devices. IP prefixes used as described above can be included in a sequential list of statements which a network protocol can sequentially walk from the first statement to the last statement looking for a match between a recently received prefix (redistributed or network address update) and information included in the statement. When the network protocol determines that there is a match between a recently received prefix and information in a statement in the prefix-list, the recently received prefix is either permitted or denied. This process is typically referred to as prefix filtering. If the prefix is permitted, the protocol can use the prefix to, among other things, update a routing or forwarding table. A recently received packet in this context can be a packet that is received from another network device or from another network protocol.
One problem with the sequential prefix-list based approach to prefix filtering is that the performance of the network device starts to degrade as the size of the prefix list increases. When the number of statements in a sequentially ordered prefix list becomes large, which can be on the order of twenty-thousand statements for example, and a match is performed for a large number of prefixes (500,000 or more as can be the case with an Internet feed), the amount of time it takes a network device to update its routing and forwarding tables increases to an unacceptable level.